package class07;

/**
 * 一颗二叉树, 存在一个特殊指针, 该指针指向父节点
 * 随机给定一个节点, 找到它的后继节点
 * 后继节点是指:在树的中序遍历(左中右)情况下, 一个节点的后继节点是谁
 *
 * 思路1: (暴力解法)
 * 先找到 parent=null 的节点(树的根节点), 然后进行中序遍历放入数组中, 之后根据指定x遍历即可
 *
 * 思路2: (根据x是否有右树进行分类讨论)
 * 1.x有右树(x为中), 那么向下x的最左节点就是x的后继节点
 * 2.x没有右树, 那么向上寻找父节点, x为父节点的左节点时, 该父节点是x的后继节点
 * 3.整棵树最右节点没有后继(向上/向下均找到null),返回null即可
 *
 *
 * 前驱节点, 同理(中序遍历, 判断左子树)
 *
 */
public class Code07_SuccessorNode {

	public static class Node {
		public int value;
		public Node left;
		public Node right;
		//指向父节点的指针
		public Node parent;

		public Node(int data) {
			this.value = data;
		}
	}

	//根据一个节点获取其后继节点
	public static Node getSuccessorNode(Node node) {
		if (node == null) {
			return node;
		}
		if (node.right != null) {
			//有右树,找到最左节点,就是后继节点
			return getLeftMost(node.right);
		} else {
			// 无右子树
			Node parent = node.parent;
			while (parent != null && parent.right == node) { // 当前节点是其父亲节点右孩子
				node = parent;
				parent = node.parent;
			}
			return parent;
		}
	}

	public static Node getLeftMost(Node node) {
		if (node == null) {
			return node;
		}
		//一直向下搜寻最左节点
		while (node.left != null) {
			node = node.left;
		}
		return node;
	}

	public static void main(String[] args) {
		Node head = new Node(6);
		head.parent = null;
		head.left = new Node(3);
		head.left.parent = head;
		head.left.left = new Node(1);
		head.left.left.parent = head.left;
		head.left.left.right = new Node(2);
		head.left.left.right.parent = head.left.left;
		head.left.right = new Node(4);
		head.left.right.parent = head.left;
		head.left.right.right = new Node(5);
		head.left.right.right.parent = head.left.right;
		head.right = new Node(9);
		head.right.parent = head;
		head.right.left = new Node(8);
		head.right.left.parent = head.right;
		head.right.left.left = new Node(7);
		head.right.left.left.parent = head.right.left;
		head.right.right = new Node(10);
		head.right.right.parent = head.right;

		Node test = head.left.left;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
		test = head.left.left.right;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
		test = head.left;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
		test = head.left.right;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
		test = head.left.right.right;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
		test = head;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
		test = head.right.left.left;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
		test = head.right.left;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
		test = head.right;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
		test = head.right.right; // 10's next is null
		System.out.println(test.value + " next: " + getSuccessorNode(test));
	}

}
